/* 空闲链表+最佳适应法 indefinite time 不建议实时任务使用 */
/* 无哨兵节点，单链结构 */

#include "heap.h"
#include <stdint.h>
#define configHEAPSIZE (4*1024)
#define ROUND_UP(X) (((X) + sizeof(size_t) - 1) & (~(sizeof(size_t) - 1)))
#define BLOCK_OFFSET(BlcokSize) ((BlcokSize) + sizeof(Node_t))

typedef struct Node_t Node_t;

struct Node_t
{
    size_t size;
    Node_t *next;
};

static _Alignas(size_t) uint8_t Heap[configHEAPSIZE];
static Node_t *pHeadNode;

void* cMalloc(size_t wantedSize)
{
    if ((wantedSize == 0) || (pHeadNode == NULL))
        return NULL;

    wantedSize = ROUND_UP(wantedSize);

    Node_t *pLastNode = NULL;
    Node_t *pCurNode = pHeadNode;
    Node_t *pBestLastNode = NULL;
    Node_t *pBestNode = NULL;
    size_t bestDiff = SIZE_MAX;

    /* 最佳适应法，找到最适合的空闲区域，遍历整个链表 */
    do
    {
        if (pCurNode->size >= wantedSize)
        {
            uint32_t thisDiff = pCurNode->size - wantedSize;
            if (bestDiff > thisDiff)
            {
                bestDiff = thisDiff;
                pBestNode = pCurNode;
                pBestLastNode = pLastNode;
            }
        }
        pLastNode = pCurNode;
        pCurNode = pCurNode->next;
    } while (pCurNode != NULL);

    /* pBestNode = NULL or IdleBlock */
    if (pBestNode == NULL)
        return NULL;

    /* pBestNode = IdleBlock */
    // 空闲块分割
    if (pBestNode->size >= BLOCK_OFFSET(wantedSize) + sizeof(size_t))
    {
        Node_t *leftBlockNode = (Node_t*)((void*)pBestNode + BLOCK_OFFSET(wantedSize));
        leftBlockNode->size = pBestNode->size - wantedSize - sizeof(Node_t);
        leftBlockNode->next = pBestNode->next;

        pCurNode = leftBlockNode;

        /* 分配空间 */
        pBestNode->size = wantedSize;
    }
    else
    {
        pCurNode = pBestNode->next;
    }

    pLastNode = pBestLastNode;

    /* 将pCurNode插入到pLastNode前 */
    if (pLastNode == NULL)
    {
        pHeadNode = pCurNode;
    }
    else
    {
        pLastNode->next = pCurNode;
    }

    return ((void*)pBestNode) + sizeof(Node_t);
}

void cFree(void* pBlock)
{
    Node_t *pNode = (Node_t*)((void*)pBlock - sizeof(Node_t));

    /* 遍历空闲列表 */
    Node_t *pRightNode = pHeadNode;
    Node_t *pLeftNode = NULL;

    /* 找到 释放的块 在空闲链表中的位置 */
    while (!((pRightNode == NULL) || (pNode <= pRightNode)))
    {
        /* 记录左侧节点 */
        pLeftNode = pRightNode;
        pRightNode = pRightNode->next;
    }
    /* pRightNode 为空闲节点或NULL 插入位置在pRightNode左侧 */

    /* 释放空闲节点 */
    if (pNode == pRightNode)
    {
        return;
    }

    /* 记录释放节点的尾边界 */
    Node_t *block_EndLimit = (Node_t*)((void*)pNode + BLOCK_OFFSET(pNode->size));

    /* 如果左节点存在，则进行左合并，否则替换头节点， */
    if (pLeftNode != NULL)
    {
        /* 记录释放节点左侧节点的尾边界 */
        Node_t *leftNode_EndLimit = (Node_t*)((void*)pLeftNode + BLOCK_OFFSET(pLeftNode->size));

        if (leftNode_EndLimit == pNode)
        {
            pLeftNode->size += BLOCK_OFFSET(pNode->size);
            pNode = pLeftNode;
        }
        else
        {
            pLeftNode->next = pNode;
        }
    }
    else
    {
        pHeadNode = pNode;
    }

    /* 如果右节点存在，则进行右合并 */
    if ((pRightNode->next != NULL) && (block_EndLimit == pRightNode))
    {
        pNode->size += BLOCK_OFFSET(pRightNode->size);
        pNode->next = pRightNode->next;
    }
    else
    {
        pNode->next = pRightNode;
    }
    
    return;
}

void HeapInit(void)
{
    /* 初始化堆 */
    pHeadNode = (Node_t*)&Heap;
    pHeadNode->size = configHEAPSIZE - sizeof(Node_t);
    pHeadNode->next = NULL;

}

/*------------------------------------------------------------------*/
#include <stdio.h>
void printIdleBlocks(void)
{
    Node_t *node = pHeadNode;
    int index = 0;

    while (node)
    {
        printf("-----------\n");
        printf("index = %d \n", index++);
        printf("Size  = %d \n", node->size);
        node = node->next;
    }
}